// *****************************************************************************
// Filename:    subset-enumeration.h
// Date:        2012-07-04 09:55
// Author:      Guangda Lai
// Email:       lambda2fei@gmail.com
// Description: TODO(laigd): Put the file description here.
// *****************************************************************************

#ifndef SUBSET_ENUMERATION_H_

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::ifstream;
using std::map;
using std::ofstream;
using std::set;
using std::string;
using std::vector;

template<typename ElementType, typename HandlerType>
void DfsForEachSubset(const vector<ElementType> &original,
                      const int subset_size,
                      const int depth,
                      HandlerType *handler,
                      vector<ElementType> *subset) {
  if (subset->size() == subset_size) (*handler)(*subset);
  if (depth == original.size()) return;
  for (int i = depth; i < original.size(); ++i) {
    subset->push_back(original[i]);
    DfsForEachSubset(original, subset_size, i + 1, handler, subset);
    subset->pop_back();
  }
}

template<typename ElementType, typename HandlerType>
void ForEachSubset(const vector<ElementType> &original,
                   const int subset_size,
                   HandlerType *handler) {
  vector<ElementType> subset;
  subset.reserve(subset_size);
  DfsForEachSubset(original, subset_size, 0, handler, &subset);
}

#define SUBSET_ENUMERATION_H_
#endif
